Computer systems typically comprise a disk storage device, for example a magnetic or optical disk drive, which provide an inexpensive means to store large amounts of digital data in a non-volatile manner. The disk storage device is essentially a communication system where the storage medium (magnetic or optical), transducer, and read/write electronics constitute the communication channel. Similar to other communication channels, the digital data in storage devices is "transmitted" through the channel by modulating an analog signal. In magnetic disk storage systems, for example, the digital data modulates the current in an inductive write coil in order to write a sequence of magnetic transitions onto the surface of a magnetic disk in concentric, radially spaced tracks. And in optical disk storage systems, the digital data may modulate the intensity of a laser beam in order to write a series of "pits" onto the surface of an optical disk in tracks that spiral inward toward the center of the disk.
During a read operation, a transducer or read head is positioned in close proximity to the surface of the disk, and while the disk spins under the read head, the read head senses the alterations (magnetic or optical) representing the digital data. The read head generates an analog read signal comprising pulses induced by the surface alterations. In magnetic recording, for example, the read head comprises a sensor that is responsive to the changes in the magnetic flux caused by the magnetic transitions representing the digital data. And in optical disk storage systems, the read head comprises a photodetector for measuring the intensity of a laser beam reflecting off the surface of the disk which changes as it passes over the pits representing the digital data.
As with other bandlimitted communication channels, the maximum capacity of a disk storage system is approximated by Shannon's equation for the capacity of an additive white Gaussian noise channel: ##EQU1##
In the above equation, W is the channel bandwidth, N.sub.0 is the noise power spectrum, and P is the signal power. The bandwidth W of a disk storage system is, for the most part, limited by the characteristics of the storage medium. Thus, once the storage medium is chosen, the maximum capacity of the storage system is essentially a function of the signal power P and the noise power N.sub.0 (i.e., the signal-to-noise ratio or SNR). Certain characteristics of the storage medium also contribute to the noise power in the read signal, so designers generally choose the least expensive medium that will provide the highest bandwidth and SNR to attain maximum storage capacity.
In addition to innovations in the storage medium itself, attempts to increase storage capacity generally focus on improving the actual SNR through improvements to the transducer and drive electronics, as well as improving the effective SNR through the use of error correction codes (ECC), such as the Reed-Solomon ECC codes, and through the use of sophisticated signal processing techniques spawned by communication theory.
One such advancement in communication theory recently applied to disk storage systems that has provided significant gains in storage capacity is partial response (PR) signaling with maximum likelihood (ML) sequence detection. Partial response signaling refers to a particular method for transmitting symbols represented as analog pulses through a communication medium. The benefit is that at the signaling instances (baud rate) there is no intersymbol interference (ISI) from other pulses except for a controlled amount from immediately adjacent, overlapping pulses. Allowing the pulses to overlap in a controlled manner leads to an increase in the symbol rate (linear recording density) without sacrificing performance in terms of SNR. Stated differently, a partial response signal provides an increase in the effective SNR by making more efficient use of the channel bandwidth.
Partial response channels are characterized by the polynomials EQU (1-D)(1+D).sup.n
where D represents a delay of one symbol period and n is an integer. For n=1,2,3, the partial response channels are referred to as PR4, EPR4 and EEPR4, with their respective frequency responses shown in FIG. 1A. The channel's dipulse response, the response to an isolated symbol, characterizes the transfer function of the system (the output for a given input). With a binary "1" bit modulating a positive dipulse response and a binary "0" bit modulating a negative dipulse response, the output of the channel y(t) is a linear combination of time shifted dipulse responses EQU y(t)=.SIGMA.a.sub.n p(t-nT)
where an denotes the write current symbols +1 and -1 at time n and p(t) represents the channel's dipulse response shifted by nT (n symbol periods). The dipulse response for a PR4 channel (1-D.sup.2) is shown as a solid line in FIG. 1B. Notice that at the symbol instances (baud rate), the dipulse response is zero except at times t=0 and t=2. Thus, the linear combination of time shifted PR4 dipulse responses will result in zero ISI at the symbol instances except where immediately adjacent pulses overlap.
It should be apparent that the linear combination of time shifted PR4 dipulse responses will result in a channel output of +2, 0, or -2 at the symbol instances (with the dipulse samples normalized to +1, 0, -1) depending on the binary input sequence. The output of the channel can therefore be characterized as a state machine driven by the binary input sequence, and conversely, the input sequence can be estimated or demodulated by running the signal samples at the output of the channel through an "inverse" state machine. Because noise will obfuscate the signal samples, the inverse state machine is actually implemented as a trellis sequence detector which computes a most likely input sequence associated with the signal samples. The algorithm for selecting a most likely sequence through a trellis was invented by a man named Viterbi, and thus the algorithm is commonly referred to as the Viterbi algorithm.
The Viterbi algorithm for a PR4 trellis sequence detector is understood from its state transition diagram shown in FIG. 2A. Each state 2 is represented by the last two input symbols (in NRZ after preceding), and each branch from one state to another is labeled with the current input symbol in NRZ 4 and the corresponding sample value 6 it will produce during readback. The demodulation process of the PR4 sequence detector is understood by representing the state transition diagram of FIG. 2A as a trellis diagram shown in FIG. 2B. The trellis diagram represents a time sequence of sample values and the possible recorded input sequences that could have produced the sample sequence. For each possible input sequence, an error metric is computed relative to a difference between the sequence of expected sample values that would have been generated in a noiseless system and the actual sample values output by the channel. For instance, a Euclidean metric is computed as the accumulated square difference between the expected and actual sample values. The input sequence that generates the smallest Euclidean metric is the most likely sequence to have generated the actual sample values; this sequence is therefore selected as the output of the sequence detector.
To facilitate the demodulation process, the sequence detector comprises path memories for storing each of the possible input sequences and a corresponding branch metric. A well known property of the sequence detector is that the paths storing the possible input sequences will "merge" into a most likely input sequence after a certain number of sample values are processed, as long as the input sequence is appropriately constrained. In fact, the maximum number of path memories needed equals the number of states in the trellis diagram; the most likely input sequence will always be represented by one of these paths, and these paths will eventually merge into one path (i.e., the most likely input sequence) after a certain number of sample values are processed.
The "merging" of path memories is understood from the trellis diagram of FIG. 2B where the "survivor" sequences are represented as solid lines. Notice that each state in the trellis diagram can be reached from one of two states; that is, there are two transition branches leading to each state. With each new sample value, the Viterbi algorithm recursively computes a new error metric and retains a single survivor sequence for each state corresponding to the minimum error metric. In other words, the Viterbi algorithm will select one of the two input branches into each state since only one of the branches will correspond to the minimum error metric, and the paths through the trellis corresponding to the branches not selected will merge into the paths that were selected. Eventually, all of the survivor sequences will merge into one path through the trellis which represents the most likely estimated data sequence to have generated the sample values as shown in FIG. 2B.
In addition to achieving maximum storage capacity, designers of disk storage systems are generally concerned with minimizing the cost, latency and power dissipation of the digital circuits which implement the signal processing algorithms. Power dissipation is of particular concern in portable applications where battery life is an important performance consideration; the more efficient the read channel circuitry, the less power it will dissipate. Latency, which is related to power dissipation, is also of particular concern as the demand for higher throughput read channels increases perpetually.
The trellis sequence detector is one of the more compute intense components of a partial response read channel, particularly the branch metric circuitry for squaring the difference between the actual signal samples and the expected samples of the target partial response, as well as the circuitry for adding-comparing-selecting (ACS) the appropriate branch metrics for each state. As described above, an error metric is computed for the two branches entering each state in the trellis; the error metric is added to the previously accumulated branch metric, compared to the contending branch metric, and the smaller of the branch metrics selected to extend the survivor sequence. Since the number of states increases exponentially with increasing partial response order (PR4, EPR4, EEPR4, etc.), so does the cost and power dissipation of the branch metric calculators and ACS circuitry. Furthermore, the latency in computing the branch metrics and performing the add-compare-select operations can adversely impact the maximum throughput of the read channel.
There is, therefore, a need for an improved sampled amplitude read channel for use in disk storage systems that employees more efficient circuitry for implementing the maximum likelihood sequence detection algorithm, such as the Viterbi algorithm. In particular, is an object of the present invention to provide more efficient branch metric calculators and ACS circuits in a trellis sequence detector in order to minimize cost and power dissipation, as well as to increase the throughput of the read channel.